package Greedy.leetcode;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      有一堆石头，每块石头的重量都是正整数。
 *      每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
 *      如果x == y，那么两块石头都会被完全粉碎；
 *      如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
 *      最后，最多只会剩下一块石头。返回此石头的重量。如果没有石
 *
 * 2. 算法分析
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 最后一块石头的重量 {
    public static void main(String[] args) {
        int[] stones = {2,7,4,1,8,1};
        int i = lastStoneWeight2(stones);
    }

    /**
     *
     * @param stones
     * @return
     */
    public static int lastStoneWeight1(int[] stones) {
        int len = stones.length;
        // 判断边界情况
        if(len == 0) {return 0;}
        if(len == 1) {return stones[0];}
        if(len == 2) {
            if(stones[0] == stones[1]) {
                return 0;
            }
            return (stones[0] < stones[1]) ? stones[1] - stones[0] : stones[0] - stones[1];
        }
        // 当石头数组的中的石头数量大于等于3时
        Arrays.sort(stones); // 升序排列
        // 此时的数组的末尾两个元素就是当前的需要比较的两个石头
        // 1 2 2
        //   i j
        int i = len - 1;
        int j = len - 2;
        int ans = 0;
        while(j < i && i >= 0 && j >= 0) {
            if(stones[i] == stones[j]) {
                // 当前两块石头全部粉碎
                j = j - 1;
                i = j - 1;
                if(i == -1) {
                    // 如果当前i为负值说明此时直接输出第1个石头的重量
                    ans = stones[0];
                    break;
                }
            }
            else if(stones[i] > stones[j]) {
                // 当前两块石头的重量不一致，粉碎重量小的一个
                int diff = stones[i] - stones[j]; // 记录当前石头的重量差值
                // 将diff插入到数组的正确的位置，不破坏数组的单调性
                int index = 0;
                for(int k = 0; k < len; k++) {
                    if(stones[k] >= diff) {
                        break;
                    }
                    index++;
                }
                // 退出循环说明当前指针k指向的元素为diff插入的位置
                // 此时需要将数组的k+1开始的元素整体向后移动一位，直接覆盖即可
                int temp = stones[index]; // 临时变量记录当前第k个石头
                // 我们的目的就是将diff插入到第k个石头的位置
                for(int s = len-1;s > index; s--) {
                    stones[s] = stones[s-1];
                }
                stones[index] = diff;
                i = j;
                j = j - 1;
            }
        }
        return stones[0];
    }


    public static int lastStoneWeight2(int[] stones) {
        if (stones.length == 1) {
            return stones[0];
        }
        Arrays.sort(stones);
        // 不是很懂下面的代码含义????淦
        while (stones[stones.length - 2] != 0) {
            stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2];
            stones[stones.length - 2] = 0;
            Arrays.sort(stones);
        }
        return stones[stones.length - 1];
    }

}
